
//branch and bound

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>  // we are using assert.h to check some conditions remain true
#include <math.h>

#define DOUB_MAX 10e30  // a large number, must be greater than max value of any solution
#define SIZE 100000 // an estimate of how large the priority queue could become
#define NITEMS 1000 // an overstimate of the number of items

int C;     // capacity of the knapsack (total weight that can be stored)
FILE *fp;
int N;     // total number of items available
int *w;  // knapsack item weights vector
int *v;  // knapsack item profits vector
int *kindex;  // a list of item indexes (we can sort these instead of moving the items)
int current_best=0;
int M=0; // the number of items currently stored in the priority queue
int QUIET=0; // can be set to 1 to suppress output
int f; // store the value of f
    
// the structure for a solution. All of this will be stored in the priority queue
typedef struct sol
{
  int string[NITEMS+1];  // binary solution vector; string[j]=1 means the jth item is in the knapsack. string[j]=0 means jth item is not in the knapsack; j = 1 to N; string[0] is meaningless and is not used.
  int val;               // solution's value
  int fixed;             // the number of items that are fixed to either 0 or 1, not *
  double bound;          // the upper bound value of the solution
}p;

p *a;  // the knapsack solutions. To be stored in a priority queue

// function prototypes
void sol_details(p *sol);
extern void read_knapsack_instance(char *filename);
extern void sort_by_ratio();
extern int print_sol2(int *s,  int *tv, int *tw);
void branch_and_bound(int *x);
void copy_string(int *from, int *to);


// The following four functions implement a priority queue.
// They are based on the functions given in Robert Sedgwick's book, Algorithms in C.
void upheap(int k)
{
  p v;
  v=a[k]; a[0].bound=DOUB_MAX;
  
  while (a[k/2].bound<=v.bound)
    {
      a[k]=a[k/2]; k=k/2;
    }
  a[k]=v;
}

void insert(p el)
{
  assert(M<SIZE-1);
  a[++M]=el;
  upheap(M);
}

void downheap(int k)
{
  int j;
  p v;
  v = a[k];
  while(k<= M/2)
    {
      j=k+k;
      if(j<M && a[j].bound<a[j+1].bound)
	j++;
      if(v.bound>=a[j].bound)
	break;
      a[k]=a[j]; k=j;
    }
  a[k]=v;
}

p _remove()
{
  p v=a[1];
  a[1]=a[M--];
  downheap(1);
  return v;
}
// End priority queue functions.


void print_sol(p *sol)
{

  int i;
  printf("%d %g ", sol->val, sol->bound);
  for(i=1;i<=sol->fixed;i++)
    printf("%d", sol->string[i]);
  while(i<=N)
    {
      printf("x");
      i++;
    }
    

  printf("\n");
}

int ww;

void frac_bound(p *x, int fix)
{
   
  // Updates the values x->val and x->bound

  // Computes the fractional knapsack upper bound
  // given a binary vector of items, where the first
  // "fix" of them are fixed. All that must be done
  // is compute the value of the fixed part; then
  // add to that the value obtained by adding in
  // items beyond the fixed part until the capacity
  // is exceeded. For the exceeded capacity, the fraction
  // of the last item added which would just fill the knapsack
  // is taken. This fraction of profit/value is added to the
  // total. This is the required upper bound.

  // Everything above assumes items are sorted in decreasing
  // profit/weight ratio

  /* YOUR CODE GOES HERE */
  ww=0;
  for (int i=1; i<=fix; i++)
  {
    if(x-> string[i] == 1)
    {
      x -> val += v[kindex[i]];
      ww += w[kindex[i]];
    }
  }

f=fix;

while(ww + w[kindex[f+1]] < C && f < N)
{
  f++;
  x -> bound += v[kindex[f]];
  ww += w[kindex[f]];
}

x -> bound += x -> val;

if ((C-ww) > 0)
{
  double leftWeight = (double)(C-ww)/(double)(w[kindex[f+1]]);
  x->bound += leftWeight * (double)v[kindex[f+1]];
} 
}
int main(int argc, char *argv[1])
{
  int *x;    // binary vector indicating items to pack
  int tv, tw; // total value and total weight of items packed  

  read_knapsack_instance(argv[1]);

  assert(NITEMS>=N);
 
  if((x = (int *)malloc((N+1)*sizeof(int)))==NULL)
    {      
      fprintf(stderr,"Problem allocating x vector\n");
      exit(1);
    }

  sort_by_ratio();

  if((a = (p *)malloc(sizeof(p)*SIZE))==NULL)
    {      
      fprintf(stderr,"Problem allocating memory for priority queue. Reduce SIZE.\n");
      exit(1);
    }

  branch_and_bound(x);
  printf("Branch and Bound Solution of Knapsack is:\n");
  print_sol2(x,&tv,&tw);
  return(0);
}


void branch_and_bound(int *x)
{
  // branch and bound

  //  start with the empty string
  // compute its value and its bound
  // put current_best = to its value
  // store it in the priority queue
  
  // LOOP until upper bound is not greater than current_best:
  // remove the first item in the queue
  // construct two children, 1 with a 1 added, 1 with a O added
  // FOREACH CHILD:
  // compute the value and bound
  // if value is greater than current_best, set current_best to it
  // add the children to the queue

  /* YOUR CODE GOES HERE */
  p parent, child1, child2;
  
  for (int i=0; i<=N; i++)
  {
    parent.string[i] = 0;
  }
  
  parent.val = 0;
  parent.fixed = 0;
  parent.bound = 0.0;
  frac_bound(&parent, parent.fixed);
  current_best = parent.val;
  insert(parent);
  
  while(a[1].bound > current_best)
  {
    
    child1 = a[1];
    child2 = a[1];
    child1.val=0;
    child1.fixed=a[1].fixed + 1;
    child1.bound=0.0;
    child2.val=0;
    child2.fixed=a[1].fixed + 1;
    child2.bound=0.0;
    child1.string[child1.fixed]=1;
    child2.string[child2.fixed]=0;
    _remove();
    
    frac_bound(&child1, child1.fixed);
    int tw1=ww;
    if (child1.val > current_best && tw1 <= C)
    {
      current_best=child1.val;
   
         for(int i=1;i<=N;i++)
      {
        x[i]=child1.string[i];
      }
    }
    
    
    
    frac_bound(&child2, child2.fixed);
    int tw2=ww;
    if (child2.val > current_best && tw2 <= C)
    {
      current_best=child2.val;
      
      for(int i=1;i<=N;i++)
      {
        x[i]=child2.string[i];
      }
      
    }
    
    if (tw1 <= C)
    {
      insert(child1);
    }
    
    if (tw2 <= C)
    {
      insert(child2);
    }
    
  }
}
  

void copy_string(int *from, int *to)
{
  int i;
  for(i=0;i<N;i++)
    {
      to[i]=from[i];
    }
}
